package org.example.top40;

public class main20 {
    //二叉树的最近公共祖先
    //思路：终止条件root为null或为目标值p、q 返回root
    //逻辑 递归left right 找到什么返回什么null left right 都有root
    public static void main(String[] args) {
        TreeNode root = builder();
        TreeNode p = root.left;
        TreeNode q = root.right;
        TreeNode node=lowerCommonAncestor(root,p,q);
        System.out.println(node.val);
    }

    private static TreeNode lowerCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q){
            return root;
        }
        TreeNode left = lowerCommonAncestor(root.left, p, q);
        TreeNode right = lowerCommonAncestor(root.right, p, q);
        if(left==null&&right==null){
            return null;
        }else if(left!=null&&right==null){
            return left;
        }else if(left==null&&right!=null){
            return right;
        }else {
            return root;
        }
    }

    private static TreeNode builder() {
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(0);
        TreeNode node6 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(4);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node4.left = node7;
        node4.right = node8;

        return root;
    }
}
